package nachos.threads;

import nachos.machine.*;

import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Vector;
import java.util.PriorityQueue;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fashion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler() {
    }

    /**
     * Allocate a new priority thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer priority from waiting threads
     *					to the owning thread.
     * @return	a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
        return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
        Lib.assertTrue(Machine.interrupt().disabled());

        Lib.assertTrue(priority >= priorityMinimum &&
                priority <= priorityMaximum);

        getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMaximum)
            return false;

        setPriority(thread, priority+1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    public boolean decreasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMinimum)
            return false;

        setPriority(thread, priority-1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;    

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {
        if (thread.schedulingState == null)
            thread.schedulingState = new ThreadState(thread);

        return (ThreadState) thread.schedulingState;
    }

    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends ThreadQueue {
    	
    	private java.util.PriorityQueue<ThreadState> queuedThreads;
    	
    	ThreadState owner;
    	
    	/**
         * <tt>true</tt> if this queue should transfer priority from waiting
         * threads to the owning thread.
         */
        public boolean transferPriority;
        
        public String toString () {
        	return owner + "\n" + queuedThreads;
        }
        
        PriorityQueue(boolean transferPriority) {
        	queuedThreads = new java.util.PriorityQueue<ThreadState>();
            this.transferPriority = transferPriority;
            this.owner = null;
        }

        public void waitForAccess(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).waitForAccess(this);
        }

        public void acquire(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).acquire(this);
        }

        public KThread nextThread() {
            Lib.assertTrue(Machine.interrupt().disabled());
            
            if (owner == null)
            	return null;
            
            // release the queue from the current owner, releasing the donated donatedPriority that thread has received 
            this.owner.ownedQueues.remove(this);
            this.owner.effPriority = this.owner.priority;	//lower effPriority to priority
            this.owner.updateEffPriorityTo(owner.calculateDonationFrom(owner.ownedQueues));	//update to receive donations
            this.owner=null;
            
	        
            ThreadState retval = this.queuedThreads.poll();
            if (retval == null)
            	return null;
            retval.acquire(this);
          
            return retval.thread;
        }

                
        /**
         * Assumes that the queue is in the correct order.
         * 
         * @return max effPriority in queue, unless the queue is empty, in which case it returns -1
         */
        public int maxEffPriority() {
        	if (this.queuedThreads != null && this.queuedThreads.peek() != null) //got null ptr here
        		return this.queuedThreads.peek().getEffectivePriority();
        	else return -1;
        }
        /**
         * Return the next thread that <tt>nextThread()</tt> would return,
         * without modifying the state of this queue.
         *
         * @return	the next thread that <tt>nextThread()</tt> would
         *		return.
         */
        protected ThreadState pickNextThread() {
            return this.queuedThreads.peek();
        }

        public void print() {
            // this is just to test out the queue and how that works... 
        	Lib.assertTrue(Machine.interrupt().disabled());
        	
        	if (this.owner != null){
        		System.out.println("Printing Queue owned by " + this.owner.thread.getName());
        	}
        	else System.out.println("Printing unowned Queue");
        	
        	if (queuedThreads.peek() == null){
        		System.out.println("empty \n");
        		return;
        	}
        	
        	java.util.PriorityQueue<ThreadState> copyOfQueuedThreads = new java.util.PriorityQueue(this.queuedThreads);
            
            while(copyOfQueuedThreads.peek() != null){
            	ThreadState tempState= (ThreadState)copyOfQueuedThreads.poll();
            	System.out.println(tempState.thread.getName()+": EffPri " + tempState.effPriority + ", Pri:" + tempState.priority);
            }
            System.out.println("");
            Lib.assertTrue(queuedThreads.peek() != null);
            
        }

        
    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see	nachos.threads.KThread#schedulingState
     */
    protected class ThreadState implements Comparable<ThreadState>{

    	protected PriorityQueue queueWaitedOn;
    	/** The thread with which this object is associated. */	   
        protected KThread thread;
        /** The priority of the associated thread. */
        protected int priority, effPriority;
        protected Vector<PriorityQueue> ownedQueues;
        protected long timeEnteredQueue;
        
        public String toString () {
        	return "TS for: " + thread + " (eP" +effPriority+"T"+timeEnteredQueue+")";
        }
        
    	/**
         * Allocate a new <tt>ThreadState</tt> object and associate it with the
         * specified thread.
         *
         * @param	thread	the thread this state belongs to.
         */
        public ThreadState(KThread thread) {
            this.thread = thread;

            setPriority(priorityDefault);
            
            queueWaitedOn= null;
            ownedQueues = new Vector<PriorityQueue>();
            timeEnteredQueue = -2;
        }
        
      
        /**
         * Return the priority of the associated thread.
         *
         * @return	the priority of the associated thread.
         */
        public int getPriority() {
            return priority;
        }
        
        /**
         * Return the effective priority of the associated thread.
         *
         * @return	the effective priority of the associated thread.
         */
        public int getEffectivePriority(){
        	return effPriority;
        }
        
        /**
         * Receives any donated priority from threads waiting on this thread.
         * These waiting are in PriorityQueues in this.ownedQueues
         * 
         * Because not all queues transfer (donate) priority,
         * 	updateEffPriority should only be used with calculateDonation,
         *  which takes this into account
         * 
         * Donates priority to the thread this one is waiting on (if any).
         * This thread is found through QueueWaitedOn
         */
        public void updateEffPriorityTo(int donatedPriority){
        	if (effPriority < donatedPriority){
        		effPriority = donatedPriority;
        		if (queueWaitedOn != null) //if this is waiting on any thread,
        			queueWaitedOn.owner.updateEffPriorityTo(this.effPriority);
        			//update that thread's priority to take into account the change
        	}
        }

        /**
         * Calculate the donation that vector of queues will give
         * @param queues
         * @return the maximum priority of all the threads of the queues. 
         * 			If there are no queues, returns -1
         */
        protected int calculateDonationFrom(Vector<PriorityQueue> queues)
        {
        	int maxSoFar = -1;
        	//for each priority queue in the vector
        	for (int i=0 ; i< queues.size(); i++){
        		if (queues.elementAt(i).transferPriority){
        			//if this queue transfers priority
        			int donated = queues.elementAt(i).maxEffPriority();
        			//find max priority of this priority
        			if (donated > maxSoFar){  //if this max is greater than maxSoFar
        				maxSoFar = donated;  //increase the max
        			}
        		}
        	}
        	
        	return Math.max(priority, maxSoFar);
        }
        
        /**
         * Set the priority of the associated thread to the specified value.
         *
         * @param	priority	the new priority.
         */
        public void setPriority(int priority) {
            if (this.priority == priority)
                return;

            this.priority = priority;
            this.effPriority = priority;
        }

        /**
         * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
         * the associated thread) is invoked on the specified priority queue.
         * The associated thread is therefore waiting for access to the
         * resource guarded by <tt>waitQueue</tt>. This method is only called
         * if the associated thread cannot immediately obtain access.
         *
         * @param	waitQueue	the queue that the associated thread is
         *				now waiting on.
         *
         * @see	nachos.threads.ThreadQueue#waitForAccess
         */
        public void waitForAccess(PriorityQueue waitQueue) {
        	initializeTimeEntered();
        	if (waitQueue.queuedThreads == null)
        		waitQueue.queuedThreads = new java.util.PriorityQueue<ThreadState> ();
            waitQueue.queuedThreads.add(this);
            this.queueWaitedOn = waitQueue;
            if(waitQueue.owner != null)
            	//waitQueue's owner's priority may need to be updated
                waitQueue.owner.updateEffPriorityTo(waitQueue.owner.calculateDonationFrom(waitQueue.owner.ownedQueues));
            	}

        /**
         * Called when the associated thread has acquired access to whatever is
         * guarded by <tt>waitQueue</tt>. This can occur either as a result of
         * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
         * <tt>thread</tt> is the associated thread), or as a result of
         * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
         *
         * @see	nachos.threads.ThreadQueue#acquire
         * @see	nachos.threads.ThreadQueue#nextThread
         */
        public void acquire(PriorityQueue waitQueue) {
            Lib.assertTrue(waitQueue.owner == null, "Acquire wasn't supposed to be called, waitQueue already has owner.");
        	//acquire is supposed to be called only when it there is no owner of the waitQueue
        	
            //setTimeEntered(-1);	
            queueWaitedOn = null;
            
            waitQueue.owner=this;
            //Lib.assertTrue(queueWaitedOn == null, "Acquiring thread is waiting on another");	//this thread cannot be waiting on another
            //Lib.assertTrue(timeEnteredQueue < 0, "Acquiring thread is still on a queue (timeEnteredQueue >= 0)");	//thus it must have no timeEnteredQueue and no queueWaitedOn
            this.ownedQueues.add(waitQueue);
            this.updateEffPriorityTo(calculateDonationFrom(this.ownedQueues));
            
        }	

        /**
         * 
         * @return a negative number if this is higher priority than otherThread, otherwise return a positive number.
         * older threads have higher priority than younger threads with the same priority value.
         */
        public int compareTo(ThreadState otherThread){
        	int priorityDiff =  ((ThreadState)otherThread).getEffectivePriority() - this.getEffectivePriority(); //other - this
        	if (priorityDiff != 0)
        		return priorityDiff; //positive iff this has lower priority. negative iff this has higher priority
        	//else, the threads have same priority value and the older one has higher priority
        	
        	if(this.timeEnteredQueue == ((ThreadState)otherThread).timeEnteredQueue)
        		return 0;		//tied
        	if(((ThreadState)otherThread).timeEnteredQueue == -1)
        		return -1;		//otherThread is not on a queue, so this has higher priority
        	if(this.timeEnteredQueue == -1)
        		return 1;		//this thread is not on a queue, so this has lower priority
        	
        	if (this.timeEnteredQueue < ((ThreadState)otherThread).timeEnteredQueue)
        		return -1;		//this is older, so it has higher priority
        	else
        		return 1;		//otherwise it has lower priority
        }
        
        private void initializeTimeEntered()
        {
        	//if (this.timeEnteredQueue < 0)
        		this.timeEnteredQueue = Machine.timer().getTime();	
        }
        
        private void setTimeEntered(long t){
        	this.timeEnteredQueue = t;
        }
    }
    
    
    
    static void selfTest() {
        PriorityScheduler p = new PriorityScheduler();
    	
    	//compareTo(ThreadState s) whitebox tests:
    	KThread t1 = new KThread();
    	ThreadState s1 = p.new ThreadState(t1);
    	s1.thread.setName("S1");
    	s1.setPriority(1);
    	s1.setTimeEntered(1);
    	
    	ThreadState s2 = p.new ThreadState(new KThread());
    	s2.thread.setName("S2");
    	s2.setPriority(2);
    	s2.setTimeEntered(2);
    	
    	ThreadState s3 = p.new ThreadState(new KThread());
    	s3.thread.setName("S3");
    	s3.setPriority(2);
    	s3.setTimeEntered(3);
    	
    	ThreadState s4 = p.new ThreadState(new KThread());
    	s4.thread.setName("S4");
    	s4.setPriority(4);
    	s4.setTimeEntered(4);
    	
    	Lib.assertTrue(s1.compareTo(s2) > 0, "Problem with compareTo method"); //s1 is lower priority than s2
    	Lib.assertTrue(s2.compareTo(s1) < 0, "Problem with compareTo method"); //s2 is higher priority than s1
    	Lib.assertTrue(s2.compareTo(s3) < 0, "Problem with compareTo method"); //s2 is higher priority than s3, even though they have the same priority values
    	 	
    	
    	//waitForAccess and other tests
    	PriorityQueue PQ = (PriorityQueue)p.newThreadQueue(true);
    	PriorityQueue PQ2 = (PriorityQueue)p.newThreadQueue(true);
    	
    	s1.acquire(PQ);
    	//confirm that s1 has acquired PQ, that PQ is owned by s1, that s1.timeEnteredQueue is initialized
    	
    	s2.waitForAccess(PQ);
    	//confirm that s3 is on PQ's queuedThreads and that s1 has received donated priority.
    	    	
    	s3.waitForAccess(PQ);
    	//confirm that s2 is on PQ's queuedThreads, before s3. This test time-based tie breaking.
    	
    	
    	boolean intStatus = Machine.interrupt().disable();
    	
    	//checking queue ordering:
    	//PQ.print();
    	
    	Lib.assertTrue(PQ.nextThread() == s2.thread);
    	
    	Machine.interrupt().restore(intStatus);
    	//confirm that s1 has released PQ, no longer receives donated priority
    	Lib.assertTrue(s1.ownedQueues.isEmpty());
    	Lib.assertTrue(s1.effPriority==s1.priority); 
    	//confirm that s2 has acquired PQ
    	Lib.assertTrue(s2.queueWaitedOn==null && s2.ownedQueues.contains(PQ));
    	//confirm that nextThread returns s2
    	
    	s1.acquire(PQ2);		//s1 acquires PQ2
    	Lib.assertTrue(s1.ownedQueues.contains(PQ2));
    	s2.waitForAccess(PQ2);	//s2 waits on s1
    	//confirm that s1 receives priority donated from s2
    	Lib.assertTrue(PQ2.queuedThreads.contains(s2) && s2.queueWaitedOn==PQ2 && s1.effPriority==s2.effPriority);
    	
    	
    	
    	s4.waitForAccess(PQ); 	//s4 waits on s2
    	//confirm that s2 receives priority from s4, and that s1 receives this new priority from s2
    	Lib.assertTrue(PQ.queuedThreads.contains(s4));
    	Lib.assertTrue(s4.queueWaitedOn==PQ);
    	Lib.assertTrue(s2.effPriority==s4.priority && s1.effPriority==s4.priority);
    	
    	s4.updateEffPriorityTo(5);
    	//confirm that s4 updates its priority and that this trickles down to s2 and then s1
    	Lib.assertTrue(s2.effPriority==5);
    	Lib.assertTrue(s1.effPriority==5);
    	
    	intStatus = Machine.interrupt().disable();
    	PQ.print();
    	PQ2.print();
    	
    	Lib.assertTrue(PQ2.owner == s1); 					//confirm that s1 owns PQ2 and receives priority from s4 through s2
    	Lib.assertTrue(s1.ownedQueues.contains(PQ2));	
    	Lib.assertTrue(s1.getEffectivePriority() == 5);
    	
    	
    	Lib.assertTrue(PQ2.nextThread() == s2.thread);	//should return s2
    	Lib.assertTrue(PQ2.nextThread() == null); //confirm that nextThread() returns null
    	Machine.interrupt().restore(intStatus);

    	Lib.assertTrue(PQ2.owner != s2); 					//confirm that nothing owns PQ2
    	Lib.assertTrue(!s2.ownedQueues.contains(PQ2));		//confirm that s1 releases PQ2 and no longer is receiving priority from s2 and s4
    	Lib.assertTrue(s1.getEffectivePriority() == 1);
    	
    	
    	//test that priority donation occurs through a lock
    	
    	
    	//check that donation occurs correctly with a mixture of queues that donate priority and queues that do not
      	intStatus = Machine.interrupt().disable();
      	System.out.println("1");
      	PQ.nextThread();
    	PQ.print();
    	PQ2.print();
    	Machine.interrupt().restore(intStatus);
    	
    	PriorityQueue nonXferQ = (PriorityQueue)p.newThreadQueue(false);
    	s1.acquire(nonXferQ);
    	s4.waitForAccess(nonXferQ);
    	
    	intStatus = Machine.interrupt().disable();
    	System.out.println("2");
    	PQ.nextThread();
    	PQ.print();
    	PQ2.print();
    	nonXferQ.print();

    	//s1.updateEffPriorityTo(s1.calculateDonationFrom(s1.ownedQueues));	//should this need to be here? it currently has to be here to work
    	System.out.println("s1 eff priority: " + s1.getEffectivePriority());
    	
    	Machine.interrupt().restore(intStatus);
    	
    	Lib.assertTrue(s1.getEffectivePriority() == s1.getPriority());		//tests that non-Xfering Queue does not transfer priority to s1
    	
    	intStatus = Machine.interrupt().disable();
    	System.out.println("3");
    	PQ.print();
    	PQ2.print();
    	nonXferQ.print();
    	Machine.interrupt().restore(intStatus);
    	
    	s1.acquire(PQ2);	//PQ2 is empty, so no priority should be donated
    	Lib.assertTrue(s1.getEffectivePriority() == 1);
    	s2.waitForAccess(PQ2);		//PQ2 is no longer empty, so s1 should receive priority
    	
    	

    	System.out.println("\nend of the testing for priority scheduler\n");
    	
    	Lib.assertTrue(s1.getEffectivePriority() == s2.getEffectivePriority());
    
    }
}
